1. Field of the Invention
The invention relates generally to the field of information storage systems used in data processing systems, and more specifically to memory stacks used in such data processing systems.
2. Description of the Prior Art
Memory stacks have been used in data processing systems for a number of purposes, including storing operands used in executing instructions, and saving the state of the host processor while it is executing subroutines or interrupt service routines. A stack is typically a sequential set of addressable storage locations in the memory having a beginning address and an end point identified by the address stored in a stack pointer register. Data may be loaded into the stack, and the contents of the stack pointer register incremented to identify the address of, or "point to", the most recently added data. In some processors, typically known as stack machines, operands are loaded into the stack in the inverse order in which they are to be used by the instructions. Each time an operand is loaded into, or "pushed onto", the stack, the stack pointer increments to identify the location in which it is stored. As each instruction is processed, the items of data on the stack required by the instruction are sequentially retrieved or "popped", from the stack and the instruction is executed. When the item is popped from the stack, the stack pointer decrements to point to the new top of the stack. The result of the processing may be returned to, or "pushed" onto, the stack after they have been processed, causing the stack pointer to again increment.
As has been mentioned, another use of a stack is to store the contents of certain of the processors' working registers while it is executing a subroutine or an interrupt service routine. When a processor interrupts the processing of one program to process another program, the state of the processor at the point at which processing of the first program is stopped must be stored while the processor is processing the other program. After the other program has been processed, the processor then retrieves the state of the prior program, and continues processing it from the point where processing was halted. The state of the processor, that is, the contents of several of its working registers, the program counter (which identifies the next instruction to be executed), and the status register are stored on, or pushed onto, the stack and are popped from the stack and returned to their previous registers when the other program has been processed. Using a stack in this manner allows nesting of interrupts or subroutines since the state of the processor during execution of the each subroutine or interrupt service routine can also be stored on the stack in response to a subsequent subroutine or interrupt service routine, and retrieved when the subsequent program has been processed.
In the prior art, data has generally been retrieved only from the top of the stack. That is, stacks are usually "last in-first out", or "LIFO", memory structures. However, in many instances it is desirable to be able to retrieve data from a stack in an order other than LIFO. For example, in many applications it would be desirable to retrieve stack data in a "FIFO", or first in-first out manner. Also, in some applications it would be advantageous to retrieve the individual items in other orders, such as LIFO or FIFO ODD or EVEN, in which the data stored at odd or even addresses are retrieved in a LIFO or FIFO mode.
In U.S. Pat. No. 3,786,432, issued to William E. Woods on Jan. 15, 1974, a memory stack having a reach down mode is described. An index register is used in conjunction with the stack pointer to identify locations in the stack from which data are retrieved. However, this arrangement would require the processor to know the number of items in the stack in order to reach a particular item.